package com.computer.fundamentals.algorithm;

import com.computer.util.Constant;
import com.computer.util.UniversalMethod;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 双指针：相比于算法，作者更偏向于认同双指针是一种思想，是对朴素线性扫描算法的一种优化
 */
public class DoublePointer {

    /**
     * 以经典问题三数之和为例(LeetCode.15):
     * 给你一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c ,使得a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0;i < nums.length;i++) {
            if (i > 0 && nums[i] == nums[i-1]) { // 去重
                continue;
            }
            int a = nums[i];
            int left = i+1, right = nums.length-1;
            while (left < right) {
                while (left < right && left > i+1 && nums[left] == nums[left-1]) {
                    left++;
                }
                while (left < right && right < nums.length-1 && nums[right] == nums[right+1]) {
                    right--;
                }
                if (left >= right) {
                    break;
                }
                int b = nums[left];
                int c = nums[right];
                if (a+b+c == 0) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(a);
                    tmp.add(b);
                    tmp.add(c);
                    res.add(tmp);
                    left++;
                }else if (a+b+c > 0) {
                    right--;
                }else if (a+b+c < 0) {
                    left++;
                }
            }
        }

        return res;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        DoublePointer doublePointer = new DoublePointer();

        System.out.println("------------原始数组------------");
        UniversalMethod.printArray(Constant.DEFAULT_THREE_SUM_TEST);
        System.out.println("\n");

        System.out.println("------------测试------------");
        List<List<Integer>> res = doublePointer.threeSum(Constant.DEFAULT_THREE_SUM_TEST);
        System.out.println(res.toString());

    }
}
